#include "myTree.h"
#include <iostream>
#include <climits>
#include <vector>
#include <algorithm>
#include <stdexcept>
using namespace std;
// 第一部分：实现树的节点类TreeNode（支持线索二叉树）和树类MyTree（支持线索二叉树），采用二叉链表存储

// TODO:树节点类的打印
void TreeNode::printNode()
{
    cout << this->data;
}
// TODO:树节点类的初始化
TreeNode::TreeNode(char a, TreeNode *left, TreeNode *right, NodeTag l, NodeTag r)
{
    data = a;
    leftChild = left;
    rightChild = right;
    lTag = l;
    rTag = r;
}
TreeNode::TreeNode()
{
    data = '\0';
    leftChild = NULL;
    rightChild = NULL;
    lTag = Link;
    rTag = Link;
}
// TODO:树节点类的销毁
TreeNode::~TreeNode()
{
    delete leftChild;
    delete rightChild;
}
// TODO:树初始化
// 初始化一棵空树
MyTree::MyTree()
{
    root = NULL;
    isThread = false;
}

// 根据二叉树的先序序列，生成二叉树的二叉链表存储,使用@表示NULL
MyTree::MyTree(const char a[])
{
    isThread = 0;
    int i = 0;
    root = generateTree(a, i);
}
// 复制构造
MyTree::MyTree(const MyTree &L)
{
    root = copyTree(L.root);
    isThread = L.isThread;
}
// TODO:树销毁：支持普通二叉树和线索二叉树
MyTree::~MyTree()
{
    destroyTree(root);
    root = NULL;
}
// 辅助函数
TreeNode *MyTree::copyTree(const TreeNode *T)
{
    if (T == NULL)
    {
        return NULL;
    }
    TreeNode *p = new TreeNode(T->data, NULL, NULL, Link, Link); // 根节点
    p->leftChild = copyTree(T->leftChild);                       // 递归copy左子树
    p->rightChild = copyTree(T->rightChild);
    return p;
}
TreeNode *MyTree::generateTree(const char pre[], int &index)
{
    if (pre[index] == '\0' || pre[index] == '@') // 空结点
    {
        index++; // 读下一个字符
        return NULL;
    }

    TreeNode *newNode = new TreeNode(pre[index], NULL, NULL, Link, Link);
    index++;

    newNode->leftChild = generateTree(pre, index);  // 递归，剩下的字符创建左子树
    newNode->rightChild = generateTree(pre, index); // 右子树

    return newNode;
}

void MyTree::destroyTree(TreeNode *p)
{
    if (isThread = 0) // 是普通二叉树
    {
        if (p == NULL) // 判断是不是结点是否为空
        {
            return;
        }
        if (p->leftChild)              // 判断左子树
            destroyTree(p->leftChild); // 递归销毁左子树
        if (p->rightChild)
            destroyTree(p->rightChild); // 递归销毁右子树
        delete p;
        p = NULL;
    }
    else
    {
        TreeNode *q;
        q = p;
        if (q == NULL)
        {
            return;
        }
        if (q->lTag == Link) // 查看ltag
            destroyTree(q->leftChild);
        if (q->rTag == Link)
            destroyTree(q->rightChild);
        delete q;
        q = NULL;
    }
}
// TODO:先序遍历二叉树并打印
// 仅支持普通二叉树，不考虑线索化，该函数不可直接递归调用，可添加必要的函数支持，对节点的访问操作为打印该节点
void MyTree::preorder(TreeNode *p)
{
    if (p == NULL)
    {
        return;
    }
    p->printNode();          // 访问根节点
    preorder(p->leftChild);  // 前序遍历左子树
    preorder(p->rightChild); /// 右
}
void MyTree::preOrderTraverse()
{
    TreeNode *p = root;
    if (isThread == 0)
    {
        preorder(p);
    }
}
// TODO:中序遍历二叉树并打印
// 支持普通二叉树与线索二叉树，该函数不可直接递归调用，可添加必要的函数支持，对节点的访问操作为打印该节点
void MyTree::inorder(TreeNode *p) // 仅用于非线索二叉树
{
    if (p == NULL)
    {
        return;
    }
    inorder(p->leftChild);  // 中序遍历左子树
    p->printNode();         // 访问根节点
    inorder(p->rightChild); // 中序遍历右子树
}
void MyTree::inOrderTraverse()
{
    TreeNode *p = root;
    if (isThread == 0) // 非线索二叉树
    {
        inorder(p);
    }
    else // 线索二叉树
    {
        TreeNode *p = root->leftChild; // 这里的root是头节点，其左孩子为根节点
        while (p != root)
        {
            while (p->lTag == Link) // 从根节点沿着左支走到头
            {
                p = p->leftChild;
            }
            cout << p->data;                                   // 访问
            while (p->rTag == Thread && p->rightChild != root) // 这里是最后一个结点
            // 如果有rtag为线索，直接访问后继，否则跳出循环，进入右孩子节点，并从右孩子节点进行右子树中序遍历
            {
                p = p->rightChild;
                cout << p->data;
            }
            p = p->rightChild;
        }
    }
}
// TODO:后序遍历二叉树并打印
// 仅支持普通二叉树，不考虑线索化，该函数不可直接递归调用，可添加必要的函数支持，对节点的访问操作为打印该节点
void MyTree::postorder(TreeNode *p)
{
    if (p == NULL)
    {
        return;
    }
    postorder(p->leftChild);  // 后序遍历左子树
    postorder(p->rightChild); // 后序遍历右子树
    p->printNode();           // 访问根节点
}
void MyTree::postOrderTraverse()
{
    TreeNode *p = root;
    if (isThread == 0)
    {
        postorder(p);
    }
}

// TODO:定位二叉树中的节点
// 在树中找到值为v的节点则返回该节点，否则返回NULL，支持普通二叉树与线索二叉树
TreeNode &MyTree::locateNode(const char &d)
{
    TreeNode *tmp = root;
    if (locate(d, tmp))
    {
        return *locate(d, tmp);
    }
    else
    {
        TreeNode *p = new TreeNode();
        return *p;
    }
}
TreeNode *MyTree::locate(const char &c, TreeNode *node)
{
    if (node->data == c) // 相等直接返回
    {
        return node;
    }

    if (node->leftChild && node->lTag != Thread) // 有左节点
    {
        TreeNode *p = locate(c, node->leftChild); // 递归调用，在左子树里找
        if (p)
        {
            return p;
        }
    }

    if (node->rightChild && node->rTag != Thread) // 有右节点
    {
        TreeNode *p = locate(c, node->rightChild); // 右子树里找
        if (p)
        {
            return p;
        }
    }
    return NULL; // 查找失败
}
// TODO:计算二叉树的叶子结点数
// 仅支持普通二叉树，不考虑线索化
int MyTree::numleaf(TreeNode *p)
{
    if (p == NULL)
    {
        return 0;
    }
    if ((p->leftChild == NULL) && (p->rightChild == NULL))
    {
        return 1;
    }
    return numleaf(p->leftChild) + numleaf(p->rightChild);
}
int MyTree::countLeaf()
{
    if (isThread == 0)
    {
        TreeNode *p = root;
        return numleaf(p);
    }
    return 0;
}
// TODO:计算二叉树的深度
// 仅支持普通二叉树，不考虑线索化
int MyTree::countHeight()
{
    return Height(root);
}

int MyTree::Height(TreeNode *p)
{
    int lh = 1, rh = 1;
    if (!p)
    {
        return 0;
    }
    lh += Height(p->leftChild);
    rh += Height(p->rightChild);
    return lh >= rh ? lh : rh;
}
// TODO:当前树是否是线索二叉树，是线索二叉树返回true，否则false
bool MyTree::isThreadedTree()
{
    return isThread;
}
TreeNode *pre = NULL; // 全局变量，代表最后一个结点
// TODO:为二叉树生成中序线索二叉树
void MyTree::threading(TreeNode *p)
{
    if (p)
    {
        threading(p->leftChild);
        if (!p->leftChild)
        {
            p->lTag = Thread;
            p->leftChild = pre;
        }
        if (!pre->rightChild)
        {
            pre->rTag = Thread;
            pre->rightChild = p;
        }
        pre = p;
        threading(p->rightChild);
    }
}
bool MyTree::inOrderThreading()
{
    TreeNode *thrt = new TreeNode;
    thrt->lTag = Link;
    thrt->rTag = Thread;
    thrt->rightChild = thrt;
    if (!root)
        thrt->leftChild = thrt;
    else
    {
        isThread = true;
        TreeNode *p = root;
        thrt->leftChild = p;
        pre = thrt;
        threading(p);
        pre->rightChild = thrt;
        pre->rTag = Thread;
        thrt->rightChild = pre;
        root = thrt;
    }
    return isThread;
}
// TODO:寻找中序线索二叉树中某节点的前驱节点 仅支持线索二叉树
TreeNode &MyTree::preNode(const TreeNode &node)
{
    TreeNode *p = node.leftChild;
    if (node.lTag == Link)
    {
        TreeNode *tmp = p;
        while (tmp->rTag == Link)
        {
            tmp = tmp->rightChild;
        }

        return *tmp;
    }
    else
        return *(node.leftChild);
}
// TODO:寻找中序线索二叉树中某节点的后继节点， 仅支持线索二叉树
TreeNode &MyTree::nextNode(const TreeNode &node)
{
    TreeNode *p = node.rightChild;
    if (node.rTag == Link)
    {
        TreeNode *tmp = p;
        while (tmp->lTag == Link)
        {
            tmp = tmp->leftChild;
        }

        return *tmp;
    }
    else
        return *(node.rightChild);
}
// 第二部分：实现霍夫曼树HuffmanTree，输出对应的霍夫曼编码

// TODO:树初始化，根据输入创建一棵霍夫曼树，第一个参数为节点个数，第二个参数为节点数组，节点值为节点重要度，越大代表越重要，要求树构建时偏小的值放入左子树，偏大的值放入右子树
HuffmanTree::HuffmanTree(const int &n, const int a[])
{
    num = n;
    int *p = new int[n];
    for (int i = 0; i < n; i++)
    {
        p[i] = a[i];
    }
    sort(p, p + n, greater<int>());
    HFT = new HFNode[n * 2];
    initleaves(n, p);
    generateCodes(n * 2 - 1, "");
    delete[] p;
}
// TODO:树销毁
HuffmanTree::~HuffmanTree()
{
    delete[] HFT;
}
void HuffmanTree::initleaves(int n, const int *data)
{
    if (n <= 1)
        return;
    int m = 2 * n - 1;
    for (int i = 1; i <= m; i++)
    {
        HFT[i].parent = 0;
        HFT[i].left = 0;
        HFT[i].right = 0;
    }
    for (int i = 1; i <= n; i++)
        HFT[i].weight = data[i - 1];
    for (int i = n + 1; i <= m; i++)
    {
        int s1, s2;
        selectMin(HFT, i, s1, s2); 
        HFT[s1].parent = i;
        HFT[s2].parent = i;
        HFT[i].left = s1;
        HFT[i].right = s2;
        HFT[i].weight = HFT[s1].weight + HFT[s2].weight;
    }
}

void HuffmanTree::selectMin(HFNode *hft, int n, int &s1, int &s2)
{
    for (int i = 1; i < n; i++)
    {
        if (HFT[i].parent == 0) 
        {
            s1 = i;
            break;
        }
    }
    for (int i = 1; i < n; i++)
    {
        if (HFT[i].parent == 0 && HFT[i].weight < HFT[s1].weight) // 找权值最小的
        {
            s1 = i;
        }
    }
    for (int i = 1; i < n; i++)
    {
        if (HFT[i].parent == 0 && i != s1)
        {
            s2 = i;
            break;
        }
    }
    for (int i = 1; i < n; i++)
    {
        if (HFT[i].parent == 0 && HFT[i].weight < HFT[s2].weight && i != s1) // 找第二小的
        {
            s2 = i;
        }
    }
}

void HuffmanTree::generateCodes(int idx, string code)
{
    HFT[idx].code = code;
    if (HFT[idx].left)
    {
        generateCodes(HFT[idx].left, code + "0");
    }
    if (HFT[idx].right)
    {
        generateCodes(HFT[idx].right, code + "1");
    }
}

void HuffmanTree::printHuffmanCodes()
{
    for (int i = 1; i <= num; i++)
    {
        cout << HFT[i].weight << ":" << HFT[i].code << endl;
    }
}
